package offer;

import java.util.Stack;

public class offerII_0039 {
    public int largestRectangleArea(int[] heights) {
        int len=heights.length;
        int[] left=new int[len];
        int[] right=new int[len];
        Stack<int[]> stack=new Stack<>();
        stack.add(new int[]{-1,-1});
        for(int i=0;i<len;++i){
            while(stack.peek()[0]>=heights[i]){
                stack.pop();
            }
            left[i]=stack.peek()[1]+1;
            stack.push(new int[]{heights[i],i});
        }
        stack.empty();
        stack.add(new int[]{-1,len});
        for(int i=len-1;i>=0;--i){
            while(stack.peek()[0]>=heights[i]){
                stack.pop();
            }
            right[i]=stack.peek()[1]-1;
            stack.push(new int[]{heights[i],i});
        }
        int max=0;
        for(int i=0;i<len;++i){
            max=Math.max(max,(right[i]-left[i]+1)*heights[i]);
        }
        return max;
    }
}
